/*
 * 百度在线网络技术（北京）有限公司拥有本软件版权2022并保留所有权利。
 * Copyright 2022, Baidu.com,Inc 2:Baidu Online Network Technology (Beijing) Co.,Ltd,
 * All rights reserved.
 */

package com.azdebugit.suanfa.test.teshuawei.test.双指针;

import java.util.HashMap;
import java.util.Map;

/**
 * Title：leetcode-76. 最小覆盖子串
 * Description：滑动窗口+Hash
 *
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
 * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * 
 * @author WZQ
 * @version 1.0.0
 * @date 2021/3/26
 */
public class Main76 {

    public String minWindow(String s, String t) {
        String res = "";
        // 窗口，统计字符的方式
        Map<Character, Integer> window = new HashMap<>();
        // 子串t字符统计
        Map<Character, Integer> chars = new HashMap<>();
        int tLen = t.length();
        int sLen = s.length();
        for (int i = 0; i < tLen; i++) {
            chars.put(t.charAt(i), chars.getOrDefault(t.charAt(i), 0) + 1);
        }

        // 双指针, left到right窗口长度 > tLen开始check
        int left = 0, right = 0, min = Integer.MAX_VALUE;
        while (right < sLen) {
            char ch = s.charAt(right);
            // 纪录到窗口
            window.put(ch, window.getOrDefault(ch, 0) + 1);
            // check成功，则left向后，压缩窗口，直到check失败，纪录min，right接着向后，依次类推
            while (check(window, chars)) {
                if ((right - left + 1) < min) {
                    min = right - left + 1;
                    res = s.substring(left, right + 1);
                }
                // left向后压缩窗口
                char ch2 = s.charAt(left);
                window.put(ch2, window.get(ch2) - 1);
                if (window.get(ch2) == 0) {
                    window.remove(ch2);
                }
                left++;
            }
            // check失败，则right继续向后，直到符合
            right++;
        }
        
        return res;
    }

    // 当前窗口是否符合题目条件
    public boolean check(Map<Character, Integer> window, Map<Character, Integer> chars) {
        for (char ch : chars.keySet()) {
            // window存在所有子串字符
            if (!window.containsKey(ch) || (window.get(ch) < chars.get(ch))) {
                return false;
            }
        }
        return true;
    }

}
